package leetcode_周赛._2023._01;

import java.util.HashMap;
import java.util.Map;

/**
 * 328 场周赛
 * AC_3
 *
 * @author yezh
 * @date 2023/1/15 11:07
 */
public class _15 {

    public static void main(String[] args) {
//        [2,3,3,3,3,1,3,1,3,2]
//        19
//        [2,1,3,1,2,2,3,3,2,2,1,1,1,3,1]
//        11
//        [2,3,1,3,2,3,3,3,1,1,3,2,2,2]
//        18
        System.out.println(new _15().countGood(new int[]{2, 3, 3, 3, 3, 1, 3, 1, 3, 2}, 19));
        System.out.println(new _15().countGood(new int[]{2, 1, 3, 1, 2, 2, 3, 3, 2, 2, 1, 1, 1, 3, 1}, 11));
        System.out.println(new _15().countGood(new int[]{2, 3, 1, 3, 2, 3, 3, 3, 1, 1, 3, 2, 2, 2}, 18));
    }

    /**
     * 6291. 数组元素和与数字和的绝对差
     * 算法：模拟
     * 数组元素肯定比数字和大, 所以直接在循环中进行减法
     */
    public int differenceOfSum(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans += num;
            while (num != 0) {
                ans -= num % 10;
                num /= 10;
            }
        }
        return ans;
    }

    /**
     * 6292. 子矩阵元素加 1
     * 算法：差分数组
     * 一维差分数组, 时间复杂度 O(n ^ 2 + nq), q --> queries 长度
     * 二维差分数组, 时间复杂度 O(n ^ 2 + 1)
     */
    public int[][] rangeAddQueries_one(int n, int[][] queries) {
        int[][] ans = new int[n][n];
        for (int[] query : queries) {
            for (int i = query[0]; i <= query[2]; i++) {
                ans[i][query[1]]++;
                if (query[3] + 1 < n) ans[i][query[3] + 1]--;
            }
        }
        for (int i = 0; i < n; i++)
            for (int j = 1; j < n; j++) ans[i][j] = ans[i][j - 1] + ans[i][j];
        return ans;
    }

    public int[][] rangeAddQueries_two(int n, int[][] queries) {
        // 设置为 n + 1 是为了减少边界判断
        // different[i][j] = ans[i][j] - ans[i][j - 1] - (ans[i - 1][j] - ans[i - 1][j - 1])
        int[][] different = new int[n + 1][n + 1];
        for (int[] query : queries) {
            int r1 = query[0], c1 = query[1], r2 = query[2], c2 = query[3];
            ++r2;
            ++c2;
            different[r1][c1]++;
            different[r1][c2]--;
            different[r2][c1]--;
            different[r2][c2]++;
        }
        int[][] tmp = new int[n + 1][n + 1];
        int[][] ans = new int[n][n];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                tmp[i][j] = tmp[i][j - 1] + tmp[i - 1][j] - tmp[i - 1][j - 1] + different[i - 1][j - 1];
                ans[i - 1][j - 1] = tmp[i][j];
            }
        return ans;
    }

    /**
     * 6293. 统计好子数组的数目
     * 算法：双指针
     * 枚举左端点
     * 从某个元素开头, 找到第一次满足 k 对相同的下标对, 如果 t >= k, 则不需要
     * 要不要执行 for 循环
     * 1、t < k, 肯定执行
     * -- 要不要 +1,
     * ---- 如果是第一次循环, 即 i == 0, 不需要 +1
     * ---- 如果不是, 需要 +1, 因为 preJ 已经遍历过了
     * 2、t >= k, 跳过
     * <p>
     * 枚举右端点
     * 遍历右端点, 计算截止右端点的最大数对
     * 再算出最大左端点的值, [left, r] 范围内肯定满足条件
     */
    public long countGood(int[] nums, int k) {
        long ans = 0;
        int pairs = 0, left = 0;
        Map<Integer, Integer> cnts = new HashMap<>();
        for (int num : nums) {
            int cnt = cnts.getOrDefault(num, 0);
            pairs += cnt;
            cnts.put(num, cnt + 1);
            cnt = cnts.getOrDefault(nums[left], 1);
            while (pairs - (cnt - 1) >= k) {
                --cnt;
                pairs -= cnt;
                cnts.put(nums[left], cnt);
                ++left;
                cnt = cnts.getOrDefault(nums[left], 1);
            }
            // left 从 0 开始算起, 所以要 +1
            if (pairs >= k) ans += left + 1;
        }
        return ans;
    }

}
